package Recursion;
import java.util.Scanner;
public class Eight_Queens {
    public static void main(String []args){
        int arr[]=new int[8];
        t a =new t();
        a.Queen(arr,0);
    }
}
class t{
    //判断位置是否正确
    //由于是一维数组表示棋盘和位置，因此行数不会相同
    //a[h] == a[i] 用于比较是否在同一列
    //Math.abs(a[h]-a[i]) == Math.abs(h-i)用于比较是否在同一个对角线（斜率）
    public boolean isok(int []a,int h){
        for(int i=0;i<h;i++){
            if(a[h] == a[i] || Math.abs(a[h]-a[i]) == Math.abs(h-i)) return false;
        }
        return true;
    }
    int count=1;//计数
    public void Queen(int a[],int h){
        if (isok(a,7)){
            //打印棋盘结果
            System.out.println((count++)+": ======================");
            for(int i=0;i<8;i++){
                for(int j=0;j<8;j++){
                    if (j==a[i]) System.out.print("Q  ");
                    else System.out.print("*  ");
                }System.out.println();
            }
            return;
        }
/*
1 第一个皇后先放第一行第一列
2 第二个皇后放在第二行第一列、然后判断是否OK，如果不OK，继续放在第二列、第三列、依次把所有列都放完，找到一个合适
3 继续第三个皇后，还是第一列、第二列直到第8个皇后也能放在一个不冲突的位置，算是找到了一个正确解
4 当得到一个正确解时，在栈回退到上一个栈时，就会开始回测，即将第一个皇后，放到第一列的所有正确解，全部得到
5 然后回头继续第一个皇后放第二列，后面继续循环执行1 2 3 4的步骤
*/
        for(int i=0;i<8;i++){
            a[h]=i;
            if(isok(a,h)){
                Queen(a,h+1);
            }
        }
    }
}